package com.fengdi.book.middle;

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.stream.Collectors;

public class LookBackSolution {
    public static class LetterCombinations {
        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<>();
            if(digits.isEmpty()) {
                return result;
            }

            HashMap<Character, String> map = new HashMap<>();
            ArrayList<Character> path = new ArrayList<>();
            // 初始化哈希表
            map.put('2' ,"abc");
            map.put('3' ,"def");
            map.put('4' ,"ghi");
            map.put('5' ,"jkl");
            map.put('6' ,"mno");
            map.put('7' ,"pqrs");
            map.put('8' ,"tuv");
            map.put('9' ,"wxyz");

            traceBack(digits, 0, result, path, map);
            return result;
        }

        private void traceBack(String digits, int depth, List<String> result, ArrayList<Character> path, HashMap<Character, String> map) {
            if(path.size() == digits.length()) {
                StringBuilder sb = new StringBuilder();
                for(Character s : path) {
                    sb.append(s);
                }
                result.add(sb.toString());
                return;
            }

            String str = map.get(digits.charAt(depth));
            for(int i = 0; i < str.length(); i++)
            {
                path.add(str.charAt(i));
                traceBack(digits, depth + 1, result, path, map);
                path.removeLast();
            }
        }
    }

    public static class GenerateParenthesis {
        private int left;
        private int right;
        private final ArrayList<String> result = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            HashMap<Character, Integer> map = new HashMap<>();
            ArrayList<Character> list = new ArrayList<>();
            map.put('(' ,0);
            map.put(')' ,0);

            this.traceBack(list, map, n);

            return this.result;
        }

        private void traceBack(ArrayList<Character> list, HashMap<Character, Integer> map, int n) {
            if(!this.isLegitimate(map) || map.get('(') > n || map.get(')') > n) return;

            if(map.get('(') == n && map.get(')') == n) {
                StringBuilder sb = new StringBuilder();
                for(Character c : list) {
                    sb.append(c);
                }
                this.result.add(sb.toString());
                return;
            }

            for(int i = 0; i < 2; i++) {
                char c = i == 0 ? '(' : ')';
                list.add(c);
                map.put(c, map.get(c) + 1);
                traceBack(list, map, n);
                list.removeLast();
                map.put(c, map.get(c) - 1);
            }
        }

        private boolean isLegitimate(HashMap<Character, Integer> map) {
            return map.get('(') >= map.get(')');
        }
    }

    public static class Permute {
        List<List<Integer>> result = new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            if(nums == null || nums.length == 0) return new ArrayList<>();

            traceBack(new ArrayList<Integer>(), nums);
            return this.result;
        }

        public void traceBack(List<Integer> list, int[] nums) {
            if(list.size() == nums.length) {
                this.result.add(new ArrayList<>(list));
                return;
            }

            for (int num : nums) {
                if (list.contains(num)) continue;
                list.add(num);
                traceBack(list, nums);
                list.removeLast();
            }
        }
    }

    public static class Subsets {
        public List<List<Integer>> result = new ArrayList<>();
        public List<List<Integer>> subsets(int[] nums) {
            if(nums.length == 0) return this.result;

            traceBack(new ArrayList<>(), nums, 0);
            return this.result;
        }

        public void traceBack(List<Integer> list, int[] nums, int index) {
            this.result.add(new ArrayList<>(list));
            for(int i = index; i < nums.length; i++) {
                list.add(nums[i]);
                traceBack(list, nums, i + 1);
                list.removeLast();
            }
        }
    }

    public  static class Exist {
        public boolean exist(char[][] board, String word) {
            char[] chars = word.toCharArray();
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    if(this.dfs(0, board, i, j, chars)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean dfs(int index ,char[][] board, int i, int j, char[] word) {
            if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word[index])
                return false;

            if(index == word.length - 1) return true;

            char tem = board[i][j];
            board[i][j] = '/';
            boolean res = this.dfs(index + 1, board, i + 1, j, word)
                    || this.dfs(index + 1, board, i - 1, j, word)
                    || this.dfs(index + 1, board, i, j + 1, word)
                    || this.dfs(index + 1, board, i, j - 1, word);
            board[i][j] = tem;
            return res;
        }
    }

    public static class SortColors {
        public void sortColors(int[] nums) {
            if(nums.length <= 1) return;
            int left = 0;
            int right = nums.length - 1;
            int index = 0;
            while(index <= right) {
                if(nums[index] == 0) {
                    swap(nums, left++, index++);
                }else if(nums[index] == 2) {
                    swap(nums, index, right--);
                }else if(nums[index] == 1) {
                    index++;
                }
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tem = nums[i];
            nums[i] = nums[j];
            nums[j] = tem;
        }
    }

    public static class TopKFrequent {
        public int[] topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                if (map.containsKey(num)) {
                    map.put(num, map.get(num) + 1);
                } else {
                    map.put(num, 1);
                }
            }

            ArrayList<Integer> list = map.entrySet().stream().sorted(Map.Entry.comparingByValue()).map(Map.Entry::getKey).collect(Collectors.toCollection(ArrayList::new));
            int[] result = new int[k];
            for(int i = k - 1; i >= 0; i--) {
                result[i] = list.removeLast();
            }
            return result;
        }
    }
}
